/**************************************************************************
 * @name:  001_插入排序.c
 * @brief: 这是插入排序代码案例
 * @date:  2025/01/02
 * @author: boluzs@163.com
 * @note: None
 * @version: 1.0.0
 * @Copyright (c) 2025 by boluzs@163.com, All Rights Reserved.
 **************************************************************************/

#include <stdio.h>
#include <stdbool.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>

void InsertSort(int *buf, int size)
{
    int i, j;
    int temp = 0;

    for (i = 1; i < size; i++)
    {
        // 备份当前元素
        temp = buf[i];

        // 先备份待插入元素的前一个元素的下标
        // 用待插入元素和有序序列的最后一个元素进行比较，如果待插入元素<有序序列的最后一个元素
        for (j = i - 1; j >= 0 && temp < buf[j]; j--)
        {
            buf[j + 1] = buf[j];
        }
        buf[j+1] = temp;
    }
}

int main()
{
    int *arr = calloc(1, sizeof(int) * 5);
    arr[0] = 3;
    arr[1] = 2;
    arr[2] = 1;
    arr[3] = 5;
    arr[4] = 4;
    InsertSort(arr, 5);
    for (int i = 0; i < 5; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    free(arr);
    return 0;
}